package com.datastructure.test.lfu;

import java.util.*;
import java.util.stream.Collectors;

public class LFU {
    public Map<Integer,ModifyTime> dataMap = new LinkedHashMap<>();
    public int time = 1;
    public int[] LFU (int[][] operators, int k) {
        // write code here
        List<Integer> data = new ArrayList<>();
        int[] result = null;
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                if (dataMap.containsKey(operator[1])) {
                    dataMap.computeIfPresent(operator[1], (key, value) -> {
                        value.modify++;
                        time++;
                        value.time=time;
                        value.value=operator[2];
                        return value;});
                } else {
                    if (dataMap.size() == k) {
                        computeNewNode();
                    } else {
                        time++;
                        dataMap.put(operator[1], new ModifyTime(1,time,operator[2]));
                    }
                }
            } else if (operator[0] == 2) {
                if(dataMap.containsKey(operator[1])){
                    data.add(dataMap.get(operator[1]).value);
                    dataMap.computeIfPresent(operator[1], (key, value) -> {
                        value.modify++;
                        time++;
                        value.time=time;
                        return value;
                    });
                } else {
                    data.add(-1);
                }
            }
        }
        result=new int[data.size()];
        for (int i = 0; i < data.size(); i++) {
            result[i]=data.get(i);
        }
        return result;
    }

    private void computeNewNode() {
        Integer modifyKey = dataMap.entrySet().stream().sorted(Comparator.comparingInt(entry -> entry.getValue().modify+entry.getValue().time))
                .limit(1).collect(Collectors.toList()).get(0).getKey();
        dataMap.remove(modifyKey);
    }

    class ModifyTime {
        public int modify;
        public int time;
        public int value;

        public ModifyTime(int modify, int time, int value) {
            this.modify = modify;
            this.time = time;
            this.value = value;
        }

        public ModifyTime(int modify, int time) {
            this.modify = modify;
            this.time = time;
        }
    }
}
